package com.leetCode.problem;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-07 16:22:22
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-07     张李鑫                     1.0         1.0 Version
 */
public class Problem41 {
    /**
     * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     *
     * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
     */

    public static void main(String[] args) {
        int []arr={2,2};
        System.out.println(firstMissingPositive(arr));
    }


    public static int firstMissingPositive(int[] nums) {
        int l=0;
        int r=nums.length;
        while (l<r){
            //如果等于l+1 把左指针往前走一步
            if (nums[l]==l+1){
                l++;
            }else if (nums[l]<=l||nums[l]>r||nums[l]==nums[nums[l]-1]){
                //3 -> 8
                //7 -> 8
                swap(nums,l,--r);
            }else {
                swap(nums,l,nums[l]-1);
            }
        }
        return l+1;
    }

    public static void swap(int []nums,int l,int j){
        int temp=nums[l];
        nums[l]=nums[j];
        nums[j]=temp;
    }
}